#! /usr/bin/python
# -*- coding: utf-8 -*-
#
# Universidad Simón Bolívar
# Ingeniería de la Computación
# Traductores e Interpretadores (CI-3725)
# Septiembre - Diciembre 2011
#
# Proyecto 1: Reconocimento de Patrones
#
# Autores:
# César Hernández  (06-39724)  <cesrafa@gmail.com>
# Daniel Valera    (07-41725)  <danielvaleradp@gmail.com>

import sys
import re
import string
import itertools

################################################################################
# Declaración de funciones
################################################################################

def readArguments(args):
  """Procedimiento que permite interpretar los argumentos ingresados por 
  consola y llenar una lista con las palabras que han de aparecer, otra para 
  las que no y una última con los nombres de los archivos que se pretenden 
  evaluar.
  
  Argumentos:
  args -- Lista de argumentos ingresados por consola."""
  
  flag = False #Indica que se han empezado a leer o no los archivos

  for arg in args:
    if (not(flag)):
      length = len(arg)
      firstLetter = arg[0]
      
      if ((length > 1) & (firstLetter == "+")):
        #Se consiguió una palabra que debe aparecer
        positives.append(arg[1:])
      elif ((length > 1) & (firstLetter == "-")):
        #Se consiguió una palabra que no debe aparecer
        negatives.append(arg[1:])
      elif (arg == "-"):
        #Se consiguió el argumento opcional menos ("-"), se empiezan a leer 
        #los nombres de los archivos
        flag = True
      elif (length > 0):
        #Se consiguió un nombre de archivo, se empiezan a leer los mismos
        archives.append(arg)
        flag = True
    else:
      archives.append(arg)

def getWithoutRepetitions(collection):
  """Función que duplica y devuelve sin repeticiones una cierta colección de 
  elementos.
  
  Argumentos:
  collection -- Colección de elementos a ser duplicada y devuelta sin 
  repeticiones."""
  
  result = []

  for element in collection:
    if (element not in result):
      result.append(element)

  return result

#def fillTables():
  #"""Procedimiento que permite llenar una tabla con las palabras que deben 
  #aparecer un número exacto de veces y otra con las que deben aparecer un 
  #mínimo número de veces."""
  
  #for word in positives:
    #if (word in negatives):
      #if (word not in exact):
        #exact[word] = 1
      #else:
        #exact[word] += 1
    #else:
      #if (word not in minimum):
        #minimum[word] = 1
      #else:
        #minimum[word] += 1

def getSeparator(words):
  """Función que devuelve parte de la expresión regular a ser utilizada; 
  específicamente, los separadores a ser utilizados entre las palabras que 
  deben aparecer en las distintas permutaciones de las mismas.
  
  Argumentos:
  words -- Lista de palabras que deben aparecer un número exacto de veces y que 
  no deben aparacer."""
  
  result = ""
  
  firstLetters = ""
  expressions = ""
  
  length = len(words)
  lastIndex = length - 1
  
  if (length > 0):
    for word in words:
      firstLetters += word[0]
      expressions += getExclusion(word)
      if (words.index(word) != lastIndex):
        expressions += "|"
    
    result = "(?:[^" + firstLetters + "]|" + expressions + ")*"
  
  return result

def getExclusion(word):
  """Función que devuelve parte de la expresión regular a ser utilizada; 
  específicamente, la que permite reconocer que una palabra no aparezca.
  
  Argumentos:
  word -- Palabra para la cual se quiere generar esta parte de la expresión 
  regular a ser utilizada."""
  
  result = word[0] + "(?:"
  stack = []
  
  i = 1
  length = len(word)
  
  while (i < length):
    letter = word[i]
    stack.append(letter)
    if (i != length - 1):
      result += letter + "(?:"
    i += 1
  
  length = len(stack)
  
  while (length > 0):
    result += "[^" + stack.pop() + "]|$)"
    if (length > 1):
      result += "|"
    length = len(stack)
  
  return result

def getExpression(separator, permutations):
  """Función que devuelve la expresión regular a ser utilizada.
  
  Argumentos:
  separator -- Parte de la expresión regular obtenida mediante la función 
  getSeparator().
  permutations -- Lista con todas las posibles permutaciones de las palabras 
  que deben aparecer."""
  
  cases = []
  
  if (len(separator) == 0):
    separator = ".*"
  
  if (len(permutations[0]) == 0):
    return "^" + separator + "$"
  elif (len(permutations[0]) == 1):
    return "^" + separator + "(?:" + permutations[0][0] + ")" + separator + "$"
  else:
    for permutation in permutations:
      cases.append(string.join(list(permutation), separator))
    
    return "^" + separator + "(?:" + string.join(cases, "|") + ")" + separator + "$"

###################
# Código auxiliar
def next_permutation(seq, pred=cmp):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""

    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    
    if not seq:
        raise StopIteration

    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")

    first = 0
    last = len(seq)
    seq = seq[:]

    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq
    
    if last == 1:
        raise StopIteration

    while True:
        next = last - 1

        while True:
            # Step 1.
            next1 = next
            next -= 1
            
            if pred(seq[next], seq[next1]) < 0:
                # Step 2.
                mid = last - 1
                while not (pred(seq[next], seq[mid]) < 0):
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                
                # Step 3.
                reverse(seq, next1, last)

                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration
###################

################################################################################
# Código principal
################################################################################

#Se leen los argumentos por consola
positives = []
negatives = []
archives = []

readArguments(sys.argv[1:])

#Se verifica la condición de tener al menos una palabra y un archivo
if (((len(positives) + len(negatives)) == 0) or (len(archives) == 0)):
  print "(!) Error: Debe introducir al menos una palabra y al menos un archivo."
  sys.exit()

#Se eliminan las repiticiones de la lista de palabras que no deben aparecer
negatives = getWithoutRepetitions(negatives)

###################
# Código auxiliar
print "positives:   ",
print positives
print "negatives:   ",
print negatives
print "archives:    ",
print archives
###################

#Se determinan las palabras que deben aparecer un número exacto de veces y las # ¿SE NECESITA?
#que deben aparecer mínimo número de veces
#exact = {}
#minimum = {}

#fillTables()

###################
# Código auxiliar
#print "exact:       ",
#print exact
#print "minimum:     ",
#print minimum
###################

#Se determinan las distintas permutaciones de las palabras que deben aparecer
permutations = getWithoutRepetitions(list(itertools.permutations(positives)))

###################
# Código auxiliar
print "permutations:    ",
print permutations
print "new permutations:",
for p in next_permutation(positives):
  print p,
print ""
###################

#Se determina la expresión regular correspondiente
expression = getExpression(getSeparator(negatives), permutations)

###################
# Código auxiliar
print "expression:   ",
print expression
###################

#Se utiliza la expresión regular para evaluar los archivos indicados
print ""

for archive in archives:
  try:
    current = open(archive, 'r')
  except IOError:
    print "(!) Error: El archivo "+archive+" no puede abrirse o no existe."
    print "Se ha omitido su lectura."
    continue
  else:
    compiled = re.compile(expression)
    for line in current:
      if (compiled.search(line)):
        print archive + ": " + line,

print ""
